Broadening the range of use of Information and Communication Technology (ICT) enables collection of various information. By performing, for example, data mining on the collected information, useful knowledge is able to be extracted.
One example of information to be collected with the ICT is information (transaction data) on product-related transactions (trading). For example, transaction data indicating items that a customer purchased at a one-time shopping is acquired via a Point Of Sales (POS) system. In this case, the transaction data is a data set that indicates a subset of all items handled by a shop.
When such transaction data is collected, a set of items which are included together (co-occur) in many pieces of transaction data may be extracted as knowledge. In this case, the set of items may be extracted under the predetermined extraction conditions which include not only whether the items are included together in many pieces of transaction data but also other various kinds of information.
The simplest way to extract a set of items satisfying predetermined conditions from data sets that are transactions each indicating a subset of all items is to confirm whether every different combination of items satisfies extraction conditions or not, and extract combinations of items satisfying the extraction conditions. However, this method has problems in which a larger number of items increase the number of combinations of items and thus considerable computational complexity is needed.
To cope with this problem, there are a variety of techniques to streamline a process for extracting a set of items under item set extraction conditions. For example, there has been proposed a symbol and numeric value basket analysis method for easily and accurately performing numeric value quantitative analysis of event occurrence relationship by searching a large number of transactions including symbol items and numeric value items. In addition, there also have been proposed efficient algorithms for graph manipulation as a technique to improve process efficiency. For example, please refer to International Publication Pamphlet No. WO 2006/057105, and J. Hoperoft, R. Tarjan, “Efficient algorithms for graph manipulation”, Communications of the ACM Volume 16 Issue 6, June 1973, p. 372-378.
However, there has been no technique to streamline a process for extracting a set of items that are included together in many of transactions collected in terms of commonality of items. Such a set of items, which are included together in many of transactions collected in terms of commonality of items, is usable for obtaining the following knowledge.
For example, from transactions indicating items ordered by customers at a restaurant, transactions are collected in terms of commonality of items. Then, from the collected transactions, a set of items that are included together in many of the transactions is extracted. A menu listing the items indicated by thus extracted set of items is a menu that covers items that are likely to be ordered together by many customers who have similar tastes. Therefore, such a menu is user friendly for many customers who have similar tastes.
In this connection, knowledge that is obtained from a set of items included together in many of transactions collected in terms of commonality of items is not limited to knowledge regarding items to be listed in a menu for a restaurant. For example, such knowledge is useful for product retail stores to determine what products are to be arranged on one shelf. In addition, such techniques using data mining to streamline a process of obtaining knowledge are generally useful techniques not only for obtaining knowledge based on transactions but also for obtaining knowledge based on a set of elements that are various kinds of information.